#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

vector<string> generateParenthesis(int n) {
    int m = n * 2;
    vector<string> res;
    string path(m, 0);

    auto dfs = [&](auto&& dfs, int i, int open) {
        if (i == m)
        {
            res.emplace_back(path);
            return;
        }

        if (open < n)
        {
            path[i] = '(';
            dfs(dfs,i + 1, open + 1);
        }
        if (i - open < open)
        {
            path[i] = ')';
            dfs(dfs,i + 1, open);
        }
    };

    dfs(dfs,0, 0);
    return res;
}